home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / programming / other / jikes / src / unzip.cpp < prev    next >
C/C++ Source or Header  |  1999-05-14  |  27KB  |  915 lines
  1. // $Id: unzip.cpp,v 1.2 1999/01/13 21:48:48 shields Exp $
  2.  
  3. //
  4. // NOTE: Jikes incorporates compression code from the Info-ZIP
  5. // group. There are no extra charges or costs due to the use of
  6. // this code, and the original compression sources are freely
  7. // available from http://www.cdrom/com/pub/infozip/ or 
  8. // ftp://ftp.cdrom.com/pub/infozip/ on the Internet.
  9. // The sole use by Jikes of this compression code is contained in the 
  10. // files unzip.h and unzip.cpp, which are based on Info-ZIP's inflate.c and 
  11. // associated header files.
  12. //
  13.  
  14. //
  15. // You can do whatever you like with this source file, though I would
  16. // prefer that if you modify it and redistribute it that you include
  17. // comments to that effect with your name and the date.  Thank you.
  18. // The abbreviated History list below includes the work of the
  19. // following:
  20. // M. Adler, G. Roelofs, J-l. Failly, J. Bush, C. Ghisler, A. Verheijen,
  21. // P. Kienitz, C. Spieler, S. Maxwell, J. Altman
  22. // Only the first and last entries from the original inflate.c are
  23. // reproduced here.
  24. //
  25.  
  26. //
  27. // History:
  28. // vers    date          who           what
  29. // ----  ---------  --------------  ------------------------------------
  30. //  a    ~~ Feb 92  M. Adler        used full (large, one-step) lookup table
  31. //  ...
  32. //  c16  20 Apr 97  J. Altman       added memzero(v[]) in huft_build()
  33. //
  34. #include "config.h"
  35. #include "unzip.h"
  36.  
  37. unsigned long Unzip::global_bb;                         /* bit buffer */
  38. unsigned Unzip::global_bk;                    /* bits in bit buffer */
  39.  
  40. unsigned Unzip::global_wp;  /* current position in slide */
  41. unsigned Unzip::global_hufts; /* huff memory usage */
  42. unsigned char Unzip::slide_buffer[32768];
  43. struct huft *Unzip::global_fixed_tl;    /* inflate static */
  44. struct huft *Unzip::global_fixed_td;    /* inflate static */
  45. int Unzip::global_fixed_bl,
  46.     Unzip::global_fixed_bd;
  47. #if defined(UNIX_FILE_SYSTEM) || defined(AMIGAOS_FILE_SYSTEM)
  48.     FILE *Unzip::global_file; /* file pointer for zip file */
  49. #elif defined(WIN32_FILE_SYSTEM)
  50.     char *Unzip::global_file; /* file pointer for zip file */
  51. #endif
  52. char *Unzip::global_bufferp; /* current position in output buffer */
  53.  
  54. /* Tables for deflate from PKZIP's appnote.txt. */
  55. unsigned Unzip::border[] = {    /* Order of the bit length code lengths */
  56.         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
  57. unsigned short Unzip::cplens[] = {         /* Copy lengths for literal codes 257..285 */
  58.         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
  59.         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
  60.         /* note: see note #13 above about the 258 in this list. */
  61. unsigned short Unzip::cplext[] = {         /* Extra bits for literal codes 257..285 */
  62.         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
  63.         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
  64. unsigned short Unzip::cpdist[] = {         /* Copy offsets for distance codes 0..29 */
  65.         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
  66.         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
  67.         8193, 12289, 16385, 24577};
  68. unsigned short Unzip::cpdext[] = {         /* Extra bits for distance codes */
  69.         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
  70.         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
  71.         12, 12, 13, 13};
  72.  
  73.  
  74. /* moved to consts.h (included in unzip.c), resp. funzip.c */
  75. /* And'ing with mask_bits[n] masks the lower n bits */
  76. unsigned short Unzip::mask_bits[] = {
  77.     0x0000,
  78.     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
  79.     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
  80. };
  81.  
  82. int Unzip::lbits = 9;           /* bits in base literal/length lookup table */
  83. int Unzip::dbits = 6;           /* bits in base distance lookup table */
  84.  
  85. struct huft *fixed_tl = (struct huft *) 0;
  86.  
  87. int Unzip::huft_build(unsigned *b,unsigned n, unsigned s, unsigned short *d, unsigned short *e, struct huft **t, int *m)
  88. /*unsigned *b             code lengths in bits (all assumed <= BMAX) */
  89. /*unsigned n              number of codes (assumed <= N_MAX) */
  90. /*unsigned s              number of simple-valued codes (0..s-1) */
  91. /* unsigned short *d                  list of base values for non-simple codes */
  92. /*ush *e                  list of extra bits for non-simple codes */
  93. /*struct huft **t         result: starting table */
  94. /*int *m                  maximum lookup bits, returns actual */
  95. /* Given a list of code lengths and a maximum table size, make a set of
  96.    tables to decode that set of codes.  Return zero on success, one if
  97.    the given code set is incomplete (the tables are still built in this
  98.    case), two if the input is invalid (all zero length codes or an
  99.    oversubscribed set of lengths), and three if not enough memory.
  100.    The code with value 256 is special, and the tables are constructed
  101.    so that no bits beyond that code are fetched when that code is
  102.    decoded. */
  103. {
  104.   unsigned a;                   /* counter for codes of length k */
  105.   unsigned c[BMAX+1];           /* bit length count table */
  106.   unsigned el;                  /* length of EOB code (value 256) */
  107.   unsigned f;                   /* i repeats in table every f entries */
  108.   int g;                        /* maximum code length */
  109.   int h;                        /* table level */
  110.   register unsigned i;          /* counter, current code */
  111.   register unsigned j;          /* counter */
  112.   register int k;               /* number of bits in current code */
  113.   int lx[BMAX+1];               /* memory for l[-1..BMAX-1] */
  114.   int *l = lx+1;                /* stack of bits per table */
  115.   register unsigned *p;         /* pointer into c[], b[], or v[] */
  116.   register struct huft *q;      /* points to current table */
  117.   struct huft r;                /* table entry for structure assignment */
  118.   struct huft *u[BMAX];         /* table stack */
  119.   unsigned v[N_MAX];            /* values in order of bit length */
  120.   register int w;               /* bits before this table == (l * h) */
  121.   unsigned x[BMAX+1];           /* bit offsets, then code stack */
  122.   unsigned *xp;                 /* pointer into x */
  123.   int y;                        /* number of dummy codes added */
  124.   unsigned z;                   /* number of entries in current table */
  125.  
  126.  
  127.   /* Generate counts for each bit length */
  128.   el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */
  129.   memset((char *)c,0, sizeof(c));
  130.   p = b;  i = n;
  131.   do {
  132.     c[*p]++; p++;               /* assume all entries <= BMAX */
  133.   } while (--i);
  134.   if (c[0] == n)                /* null input--all zero length codes */
  135.   {
  136.     *t = (struct huft *)0;
  137.     *m = 0;
  138.     return 0;
  139.   }
  140.  
  141.  
  142.   /* Find minimum and maximum length, bound *m by those */
  143.   for (j = 1; j <= BMAX; j++)
  144.     if (c[j])
  145.       break;
  146.   k = j;                        /* minimum code length */
  147.   if ((unsigned)*m < j)
  148.     *m = j;
  149.   for (i = BMAX; i; i--)
  150.     if (c[i])
  151.       break;
  152.   g = i;                        /* maximum code length */
  153.   if ((unsigned)*m > i)
  154.     *m = i;
  155.  
  156.  
  157.   /* Adjust last length count to fill out codes, if needed */
  158.   for (y = 1 << j; j < i; j++, y <<= 1)
  159.     if ((y -= c[j]) < 0)
  160.       return 2;                 /* bad input: more codes than bits */
  161.   if ((y -= c[i]) < 0)
  162.     return 2;
  163.   c[i] += y;
  164.  
  165.  
  166.   /* Generate starting offsets into the value table for each length */
  167.   x[1] = j = 0;
  168.   p = c + 1;  xp = x + 2;
  169.   while (--i) {                 /* note that i == g from above */
  170.     *xp++ = (j += *p++);
  171.   }
  172.  
  173.  
  174.   /* Make a table of values in order of bit lengths */
  175.   memset((char *)v,0, sizeof(v));
  176.   p = b;  i = 0;
  177.   do {
  178.     if ((j = *p++) != 0)
  179.       v[x[j]++] = i;
  180.   } while (++i < n);
  181.   n = x[g];                     /* set n to length of v */
  182.  
  183.  
  184.   /* Generate the Huffman codes and for each, make the table entries */
  185.   x[0] = i = 0;                 /* first Huffman code is zero */
  186.   p = v;                        /* grab values in bit order */
  187.   h = -1;                       /* no tables yet--level -1 */
  188.   w = l[-1] = 0;                /* no bits decoded yet */
  189.   u[0] = (struct huft *)0;   /* just to keep compilers happy */
  190.   q = (struct huft *)0;      /* ditto */
  191.   z = 0;                        /* ditto */
  192.  
  193.   /* go through the bit len